package com.base.leetcode;

import com.base.dataStructure.Tree.TreeNode;

import java.util.LinkedList;

/**
 * @Author: hdhao
 * @Create: 2023/4/9 - 13:58
 * @Version: v1.0
 */
//验证一棵二叉树是否是合法的二叉搜索树
public class Leetcode98 {

    //非递归实现
    public boolean isValidBST(TreeNode node) {
        TreeNode p = node;
        LinkedList<TreeNode> stack = new LinkedList<>();
        long prev = Long.MIN_VALUE;//代表上一个值
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode pop = stack.pop();
                //处理值
                if (prev >= pop.val) {
                    return false;
                }
                prev = pop.val;
                p = pop.right;
            }
        }
        return true;
    }
    //递归实现
    public boolean isValidBST1(TreeNode node) {
        if (node == null) {
            return true;
        }
        long prev = Long.MIN_VALUE;
        boolean a = isValidBST1(node.left);
        if (!a) {
            return false;
        }
        //值
        if (prev >= node.val) {
            return false;
        }
        prev = node.val;
        boolean b = isValidBST1(node.right);
        return isValidBST1(node.right);
    }
    //通过上下限来判断
    public boolean isValidBST2(TreeNode node) {
        return doValid(node, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean doValid(TreeNode node, long min, long max){
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        boolean a = doValid(node.left, min, node.val);//左孩子递归校验
        boolean b = doValid(node.right, node.val, max);//左孩子递归校验
        return a && b;
    }
}
